A stack is a data structure in which only the top element can be accessed. To illustrate, the plates stored in the spring-loaded device in a buffet line perform like a stack. A customer always takes the top plate; when a plate is removed, the plate beneath it moves to the top. The last plate placed on the stack is the first removed; a stack is therefore a last-in, first-out (LIFO) structure.
A queue is a data structure that models a real-life queue in a bank
or other service situation. New arrivals get on at the end of the queue;
customers are removed from the front of the queue as they are served. The
earliest arrival in a queue is the first to be served, so the queue is a
first-in, first out (FIFO) structure.
Implementing Stacks Using Linked Lists
The following diagram shows a stack of three characters. The letter C, the character at the top of the stack, is the only one we can access. We must remove C from the stack in order to access the symbol +. Removing a value from a stack is called popping the stack, and storing a data item in a stack is called pushing it onto the stack.
We can implement a stack as a linked list in which all insertions and deletions are performed at the list head. A list representation of the stack containing C, +, and 2 is:
Next we draw the stack after we push the symbol * onto it:
If we pop this stack, we restore the stack to its earlier state.
Program 14.14 gives a specification for a generic stack package.
Program 14.14
WITH Lists_Generic;
GENERIC
TYPE StackElement IS PRIVATE;
PACKAGE Stacks_Generic IS
------------------------------------------------------------------------
--| Generic package for LIFO stacks
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
-- type definition
TYPE Stack IS LIMITED PRIVATE;
-- exported exceptions
StackEmpty : EXCEPTION;
-- constructors
PROCEDURE MakeEmpty (S : IN OUT Stack);
-- Pre: S is defined
-- Post: S is empty
PROCEDURE Push (S : IN OUT Stack; E : IN StackElement);
-- Pre: S and E are defined
-- Post: S is returned with E as the top StackElement
PROCEDURE Pop (S : IN OUT Stack);
-- Pre: S is defined
-- Post: S is returned with the top StackElement discarded
-- Raises: StackEmpty if S contains no StackElements
-- selector
FUNCTION Top (S : IN Stack) RETURN StackElement;
-- Pre: S is defined
-- Post: The top StackElement of S is returned
-- Raises: StackEmpty if S contains no StackElements
-- inquiry operations
FUNCTION IsEmpty (S : IN Stack) RETURN Boolean;
-- Pre: S is defined
-- Post: returns True if S is empty, False otherwise
PRIVATE
PROCEDURE Dummy (Item: StackElement);
PACKAGE Lists IS
NEW Lists_Generic(ElementType => StackElement, DisplayElement => Dummy);
TYPE Stack IS RECORD
Store : Lists.List;
END RECORD;
END Stacks_Generic;
This
package takes a single generic parameter, StackElement, and
represents a stack as a LIMITED PRIVATE type, implemented as a
record containing a linked list as its only field. The package provides an
exception, StackEmpty, which is raised if a client program
attempts to pop, or retrieve the top element of, an empty stack. The operations
are easily understood from the postconditions.
The PRIVATE section of
Program
14.14 warrants explanation. Because Lists_Generic requires two
generic parameters, we must supply these when we instantiate. The element
parameter in the instantiation of Lists_Generic is obvious; the
second parameter is a procedure Dummy whose specification is given
in the PRIVATE section. We are not interested in displaying the
full contents of the stack, so the stack package contains no call to the linked
list Display procedure. We therefore provide a do-nothing
procedure, just to satisfy the requirements of the list package. The body of
Dummy, which is never called but must be given in the body of
Stacks_Generic, is just
PROCEDURE Dummy (Item: StackElement) IS
BEGIN
NULL;
END Dummy;
As an exercise, you can complete the stack package. Doing so is
easy because you have the list package already available. Push
will contain a call to AddToFront, Pop will contain a
call to RemoveFront, and Top will contain a call to
RetrieveFront.
Stack Applications
In
Section
13.2, we showed how compilers use stacks to store procedure and function
parameters. Compilers also use stacks for data storage while translating
expressions. In general, we use stacks in a program to remember a sequence of
data objects or actions in the reverse order from that in which they were
encountered. Stacks are often an alternative to recursion. To show this,
consider a nonrecursive version of StringReverse, which was given
as a recursive function in
Program
13.8. The algorithm for this function is
Algorithm for Nonrecursive String Reverse
1. Create an empty stack.
2. Push each data character in the input string onto the stack.
3. Retrieve each character from the stack, copy it into the output string, then pop the stack.
Step 2 Refinement
2.1 FOR each character in the input string LOOP
2.2 Push the character onto the stack
END LOOP;
Step 3 Refinement
3.1 FOR each character in the stack LOOP
3.2 Copy the character into the output string
3.3 Pop the stack
END LOOP;
Try carrying out this algorithm by hand. Draw a picture of the stack, then push
into it the letters of the word house. Popping the characters into
the output string will produce the string esouh. Make sure you
understand the algorithm.
Program
14.15 shows a function implementing this algorithm.
Program 14.15
FUNCTION StringReverse(S: String) RETURN String IS
------------------------------------------------------------------------
--| Returns the reverse of a string, using a stack instead of recursion
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
-- Pre: S is defined
-- Post: returns the reverse of S
PACKAGE Char_Stacks IS
NEW Stacks_Generic(StackElement => Character);
USE Char_Stacks;
OneStack: Stack;
Result: String (S'Range);
BEGIN -- StringReverse
IF S'Length <= 1 THEN
RETURN S;
END IF;
MakeEmpty (OneStack);
FOR Count IN S'Range LOOP
Push (OneStack, S(Count));
END LOOP;
FOR Count IN Result'Range LOOP
Result (Count) := Top (OneStack);
Pop (OneStack);
END LOOP;
RETURN Result;
END StringReverse;
In
this function, which might be included in a program like
Palindrome (
Program
13.8), Stacks_Generic is instantiated for the type
Character, then the algorithm is translated straightforwardly into
Ada.
Another application of a stack is to determine whether the parentheses in an expression are balanced. For example, the expression
(a + b * (c / (d - e))) + (d / e)
1 2 3 321 1 1
has balanced parentheses. We can solve this problem without
using a stack by ignoring all characters except the symbols ( and ). We start a
counter at 1 and add 1 for each open parenthesis that follows another open
parenthesis and subtract 1 for each closed parenthesis that follows another
closed parenthesis. Because we are ignoring all other symbols, the parentheses
being considered do not have to be consecutive characters. If the expression is
balanced, the final count will be 1, and it will always be positive.
This task becomes more difficult if we expand our notion of parentheses to include braces and brackets. For example, the expression
(a + b * {c / [d - e]}) + (d / e)
is balanced, but the expression
(a + b * {c / [d - e}) + (d / e)
is not because the subexpression [d - e} is
incorrect.
PROBLEM SPECIFICATION
The set of open parenthesis symbols is {, [, and (. An expression is balanced if each subexpression that starts with the symbol { ends with the symbol }; the same is true for the symbol pairs [ ] and ( ). In other words, the unmatched open parenthesis nearest to each closed parenthesis must have the correct shape (e.g., if } is the closed parenthesis in question, the symbol { must be the nearest unmatched open parenthesis).
ANALYSIS
Solving this problem without stacks would be fairly difficult, but with stacks it becomes easy. First, scan the expression from left to right, ignoring all characters except for parenthesis symbols (including braces and brackets). Push each open parenthesis symbol onto a stack of characters. For a closed parenthesis symbol, pop an open parenthesis from the stack and see whether it matches the closed parenthesis. If the symbols don't match or the stack is empty, there is an error in the expression. If they do match, continue the scan.
Data Requirements
Problem Input
Expression: String (expression to be checked for balanced
parentheses)
Problem Output
The function result indicating whether the parentheses in
Expression are balanced
Program Variables
stack of open parentheses (ParenStack: Stack)
next character in input expression (NextChar : Character)
open parenthesis at top of stack (OpenParen : Character)
index to Expression (Index : Positive)
program flag (Balanced : Boolean)
DESIGN
Initial Algorithm
1 Create an empty stack of characters.
2. Assume that the expression is balanced (Balanced is
True).
3. WHILE we are still in the expression and the expression is
balanced LOOP
4. Get the next character in the expression.
5. IF the next character is an open parenthesis
THEN
6. Push it onto the stack.
ELSIF the next character is a closed parenthesis
THEN
7. Pop the top of the stack.
END IF;
8. IF stack was empty or its top was incorrect THEN
9. Set Balanced to False.
END IF;
END LOOP;
10. The expression is balanced if Balanced is True
and the stack is empty.
The IF statement in step 5 tests each character in the expression,
ignoring all characters except for open and closed parenthesis symbols. If the
next character is an open parenthesis symbol, it is pushed onto the stack. If
the next character is a closed parenthesis symbol, the nearest unmatched open
parenthesis is retrieved (by popping the stack) and compared to the closed
parenthesis (steps 7 and 8). If the next character is not an open or closed
parenthesis symbol, it is ignored.
IMPLEMENTATION
Program 14.16 shows a function that determines whether its input parameter (an expression) is balanced.
Program 14.16
IsBalanced
FUNCTION IsBalanced (Expression: String) RETURN Boolean IS
------------------------------------------------------------------------
--| Determines whether a string is balanced with respect to
--| parentheses (), [], and {}
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
-- Pre: Expression is defined
-- Post: Returns True if Expression is balanced, False otherwise
PACKAGE Char_Stacks IS NEW Stacks_Generic(StackElement => Character);
USE Char_Stacks;
ParenStack: Stack; -- stack of open parentheses
NextChar : Character; -- next character in input expression
OpenParen : Character; -- open parenthesis at top of stack
Index : Positive; -- index to Expression
Balanced : Boolean; -- program flag
BEGIN -- IsBalanced
MakeEmpty (ParenStack);
Balanced := True;
Index := Expression'First;
WHILE Index <= Expression'Last AND THEN Balanced LOOP
-- Invariant:
-- All close parentheses so far were matched and Index
-- is within the range of Expression
NextChar := Expression (Index);
CASE NextChar IS
WHEN '(' | '[' | '{' =>
Push (ParenStack, NextChar); -- Push open parenthesis
WHEN ')' | ']' | '}' =>
IF IsEmpty (ParenStack) THEN
Balanced := False;
ELSE
OpenParen := Top (ParenStack); -- Get nearest open paren
Pop (ParenStack);
CASE NextChar IS -- Do open and close match?
WHEN ')' =>
Balanced := OpenParen = '(';
WHEN ']' =>
Balanced := OpenParen = '[';
WHEN '}' =>
Balanced := OpenParen = '{';
WHEN OTHERS =>
NULL;
END CASE;
END IF;
WHEN OTHERS =>
NULL;
END CASE;
Index := Index + 1; -- move on to next character
END LOOP;
RETURN Balanced AND IsEmpty (ParenStack);
END IsBalanced;
The
IF statement from step 5 of the algorithm is in fact written as a
CASE statement, which more easily tests for open and closed
parentheses. Each open parenthesis is pushed onto stack
ParenStack. For each closed parenthesis, Top
retrieves the nearest unmatched open parenthesis from the stack and
Pop pops the stack. If the stack is empty, Balance is
set to False, causing the WHILE loop exit. Otherwise,
the CASE statement sets Balanced to indicate whether
the character popped matches the current closed parenthesis symbol. After loop
exit occurs, the function result is returned. It is True only when
the expression is balanced and the stack is empty.
A queue can be used to model any kind of queueing situation, such as a line of customers waiting at a checkout counter or a stream of jobs waiting to be printed by a printer. For example, here is a linked list representing a queue of three students waiting to speak to their advisor, who insists on strict FIFO order in student conferences.
The name of the student who has been waiting the longest is Kann (pointed to by the head pointer); the name of the most recent arrival is Rajwan (pointed to by the tail pointer). Kann will be the first one to leave the queue when the advisor becomes available, and the head pointer will be reset to point to Choi. Any new students will be added to the end of the queue after Rajwan. Here is the queue after Kann leaves it:
Here is the queue after Perez arrives:
Program 14.17 gives the specification for a generic queue package. It is similar to the stack package in its structure.
Program 14.17
WITH Lists_Generic;
GENERIC
TYPE QueueElement IS PRIVATE;
PACKAGE Queues_Generic IS
------------------------------------------------------------------------
--| Generic package for FIFO queues
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
-- type definition
TYPE Queue IS LIMITED PRIVATE;
-- exported exceptions
QueueEmpty : EXCEPTION;
-- constructors
PROCEDURE MakeEmpty (Q : IN OUT Queue);
-- Pre: Q is defined
-- Post: Q is empty
PROCEDURE Enqueue (Q : IN OUT Queue; E : IN QueueElement);
-- Pre: Q and E are defined
-- Post: Q is returned with E as the last QueueElement
PROCEDURE Dequeue (Q : IN OUT Queue);
-- Pre: Q is defined
-- Post: Q is returned with the first QueueElement discarded
-- Raises: QueueEmpty if Q contains no QueueElements
-- selector
FUNCTION First (Q : IN Queue) RETURN QueueElement;
-- Pre: Q is defined
-- Post: The first QueueElement of Q is returned
-- Raises: QueueEmpty if Q contains no QueueElements
-- inquiry operations
FUNCTION IsEmpty (Q : IN Queue) RETURN Boolean;
-- Pre: Q is defined
-- Post: returns True if Q is empty, False otherwise
PRIVATE
PROCEDURE Dummy (Item: QueueElement);
PACKAGE Lists IS
NEW Lists_Generic(ElementType => QueueElement,
DisplayElement => Dummy);
TYPE Queue IS RECORD
Store : Lists.List;
END RECORD;
END Queues_Generic;
We
leave it as an exercise to complete the package body for this package. As in
the stack package, the queue operations are easily written in terms of the list
ones. Enqueue will call AddToEnd,
Dequeue will call RemoveFront, and so on.
Copyright © 1996 by Addison-Wesley Publishing Company, Inc.