Chapter 5: Stacks and Queues
Stacks
• A stack is a container of objects that are inserted and
removed according to the last- in first-out (LIFO)
principle
• Objects can be inserted into a stack at any time, but
only the most recently inserted (that is, “last”) object
can be removed at any time
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
• 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
•
Loading…
“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
• Operations:
− Push: to add an element onto the stack
− Pop: to remove an element from the stack
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Example
Example 5.1: Internet Web browsers store the
addresses of recently visited sites on a stack. Each time
a user visits a new site, that site’s address is “pushed”
onto the stack of addresses. The browser then allows
the user to “pop” back to previously visited sites using
the “back” button.
•Example 5.2: Text editors usually provide an “undo”
mechanism that cancels recent editing operations and
reverts to former states of a document. This undo
operation can be accomplished by keeping text changes
in a stack
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
The Stack Abstract Data Type
• Stacks are the simplest of all data structures, yet they
are also among the most important, since they are
used in a host of different applications that include
many more sophisticated data structures. Formally, a
Loading…
stack is an abstract data type (ADT) that supports the
following operations:
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
• push(e): Insert element e at the top of the stack.
• pop(): Remove the top element from the stack; an
error occurs if the stack is empty.
• top(): Return a reference to the top element on the
stack, without removing it; an error occurs if the
stack is empty
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
• Additionally, let us also define the following
supporting functions:
• size(): Return the number of elements in the stack.
• empty(): Return true if the stack is empty and false
otherwise.
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Example 5.3: The following table shows a series of stack
operations and their effects on an initially empty stack of
integers.
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Implementation of Stacks as Arrays
• First element can go in first array position, the
second in the second position, etc.
• The top of the stack is the index of the last
element added to the stack
• Stack elements are stored in an array
• Stack element is accessed only through top
• To keep track of the top position, use a
variable called stackTop
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Implementation of Stacks as Arrays
(continued)
• Because stack is homogeneous
− You can use an array to implement a stack
• Can dynamically allocate array
− Enables user to specify size of the array
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Loading…
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Implementation of Stacks as Arrays
(continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Implementation of Stacks as Arrays
(continued)
• C++ arrays begin with the index 0
− Must distinguish between:
• The value of stackTop
• The array position indicated by stackTop
• If stackTop is 0, the stack is empty
• If stackTop is nonzero, the stack is not
empty
− The top element is given by stackTop - 1
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Implementation of Stacks as Arrays
(continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Initialize Stack
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Empty Stack
• If stackTop is 0, the stack is empty
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Full Stack
• The stack is full if stackTop is equal to
maxStackSize
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push
• Store the newItem in the array component
indicated by stackTop
• Increment stackTop
• Must avoid an overflow
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push (continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Return the Top Element
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Pop
• Simply decrement stackTop by 1
• Must check for underflow condition
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Constructor
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Destructor
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Stack Header File
• Put definitions of class and functions (stack
operations) together in a file
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
… Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Loading…
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Linked Implementation of Stacks
• Array only allows fixed number of elements
• If number of elements to be pushed exceeds
array size
− Program may terminate
• Linked lists can dynamically organize data
• In a linked representation, stackTop is
pointer to top element in stack
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Default Constructor
• Initializes the stack to an empty state when a
stack object is declared
− Sets stackTop to NULL
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Empty Stack and Full Stack
• In the linked implementation of stacks, the
function isFullStack does not apply
− Logically, the stack is never full
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Initialize Stack
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push
• The newElement is added at the beginning
of the linked list pointed to by stackTop
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push (continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push (continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push (continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Push (continued)
• We do not need to check whether the stack is
full before we push an element onto the stack
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Return the Top Element
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
. Pop
• Node pointed to by stackTop is removed
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Pop (continued)
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science
Destructor
Data Structures and Algorithms in C++ Second Edition Michael T. Goodrich - Department of 0
Computer Science