VJC Chapter 15 Stack and Queue

Chapter 15 Stack and Queue Contents 1 Stack 1.1 Stack implementation 2 Queue 2.1 Linear queue implementation 2.2 Circular queue implementation Syllabus Learning Outcomes 1.3 Data Structures Understand concept and write algorithms for stack, queue (linear and circular), linear linked list and binary search tree. 1.3.3 Create, insert, and delete operations for stack and queue (linear and circular). 2.3 Implementing Algorithms and Data Structures Use programming language elements and constructs to implement sort and search algorithms such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search and hash table search, as well as data structures such as stacks, queues, linear linked lists and binary search trees. 2.3.3 Write programs to implement operations for stacks, queues (linear and circular), linear linked lists and binary search trees. 1

1. Stack Stack is an abstract data type (ADT) which inserts and removes items according to the Last-In-First-Out ( LIFO ) principle. A user may insert items into a stack at any time, but may only access or remove the last item inserted. The name “stack” is derived from the metaphor of a stack of plates in a spring-loaded, cafeteria plate dispenser. In this case, the fundamental operations involve the “pushing” and “popping” of plates on the stack. When we need a new plate from the dispenser, we “pop” the top plate off the stack, and when we add a plate, we “push” it down on the stack to become the new top plate. The same terms are also used in the stack ADT. Stacks are used in many applications such as the Internet Web browsers storing the addresses of recently visited sites, reversing data as well as matching opening and closing symbols. 1.1 Stack implementation Stack can be implemented using either array or linked list. The basic operations of a stack is to ● push(): add an item to the top of the stack ● pop(): remove and return an item from the top of the stack Other supporting operations to be added are ● is_empty(): check if stack is empty ● size(): return number of items in the stack ● peek(): return the top item without removing it ● display(): show all items in the stack Implementation using array Implementation using linked list 2

2. Queue Queue is another ADT which is a collection of items that are inserted and removed according to the First-In-First-Out (FIFO) principle. That is, items can