Stack and List Buffers Notes | EduRev

: Stack and List Buffers Notes | EduRev

 Page 1


Stack and List Buffers 
Eric Roberts 
CS 106B 
May 1, 2009 
Page 2


Stack and List Buffers 
Eric Roberts 
CS 106B 
May 1, 2009 
Where Do We Go From Here? 
• Our strategy for the next two days is to implement the class 
EditorBuffer in three different ways and to compare the 
algorithmic efficiency of the various options.  Those three 
representations are: 
A simple array model. 1. 
A two-stack model that uses a pair of character stacks. 2. 
A linked-list model that uses pointers to indicate the order. 3. 
• For each model, we’ll calculate the complexity of each of the 
six fundamental methods in the EditorBuffer class.  Some 
operations will be more efficient with one model, others will 
be more efficient with a different underlying representation. 
Page 3


Stack and List Buffers 
Eric Roberts 
CS 106B 
May 1, 2009 
Where Do We Go From Here? 
• Our strategy for the next two days is to implement the class 
EditorBuffer in three different ways and to compare the 
algorithmic efficiency of the various options.  Those three 
representations are: 
A simple array model. 1. 
A two-stack model that uses a pair of character stacks. 2. 
A linked-list model that uses pointers to indicate the order. 3. 
• For each model, we’ll calculate the complexity of each of the 
six fundamental methods in the EditorBuffer class.  Some 
operations will be more efficient with one model, others will 
be more efficient with a different underlying representation. 
The EditorBuffer Class 
• The EditorBuffer class supports the following operations: 
buffer.moveCursorForward() 
Moves the cursor forward one character (does nothing if it’s at the end). 
buffer.moveCursorBackward() 
Moves the cursor backward one character (does nothing if it’s at the beginning). 
buffer.moveCursorToStart() 
Moves the cursor to the beginning of the buffer. 
buffer.moveCursorToEnd() 
Moves the cursor to the end of the buffer. 
buffer.insertCharacter(ch) 
Inserts the character ch at the cursor position and advances the cursor past it. 
buffer.deleteCharacter() 
Deletes the character after the cursor, if any. 
buffer.display() 
Displays the buffer on cout (primarily for debugging). 
Page 4


Stack and List Buffers 
Eric Roberts 
CS 106B 
May 1, 2009 
Where Do We Go From Here? 
• Our strategy for the next two days is to implement the class 
EditorBuffer in three different ways and to compare the 
algorithmic efficiency of the various options.  Those three 
representations are: 
A simple array model. 1. 
A two-stack model that uses a pair of character stacks. 2. 
A linked-list model that uses pointers to indicate the order. 3. 
• For each model, we’ll calculate the complexity of each of the 
six fundamental methods in the EditorBuffer class.  Some 
operations will be more efficient with one model, others will 
be more efficient with a different underlying representation. 
The EditorBuffer Class 
• The EditorBuffer class supports the following operations: 
buffer.moveCursorForward() 
Moves the cursor forward one character (does nothing if it’s at the end). 
buffer.moveCursorBackward() 
Moves the cursor backward one character (does nothing if it’s at the beginning). 
buffer.moveCursorToStart() 
Moves the cursor to the beginning of the buffer. 
buffer.moveCursorToEnd() 
Moves the cursor to the end of the buffer. 
buffer.insertCharacter(ch) 
Inserts the character ch at the cursor position and advances the cursor past it. 
buffer.deleteCharacter() 
Deletes the character after the cursor, if any. 
buffer.display() 
Displays the buffer on cout (primarily for debugging). 
The Two-Stack Model 
• In the two-stack implementation of the EditorBuffer class, 
the characters in the buffer are stored in one of two stacks.  
The characters before the cursor are stored in a stack called 
before and the characters that follow the cursor are stored in 
a stack called after.  Characters in each stack are stored so 
that the ones close to the cursor are near the top of the stack. 
• For example, given the buffer contents 
a b c d e 
 the characters would be stored like this: 
before after 
a 
b 
c 
e 
d 
Page 5


Stack and List Buffers 
Eric Roberts 
CS 106B 
May 1, 2009 
Where Do We Go From Here? 
• Our strategy for the next two days is to implement the class 
EditorBuffer in three different ways and to compare the 
algorithmic efficiency of the various options.  Those three 
representations are: 
A simple array model. 1. 
A two-stack model that uses a pair of character stacks. 2. 
A linked-list model that uses pointers to indicate the order. 3. 
• For each model, we’ll calculate the complexity of each of the 
six fundamental methods in the EditorBuffer class.  Some 
operations will be more efficient with one model, others will 
be more efficient with a different underlying representation. 
The EditorBuffer Class 
• The EditorBuffer class supports the following operations: 
buffer.moveCursorForward() 
Moves the cursor forward one character (does nothing if it’s at the end). 
buffer.moveCursorBackward() 
Moves the cursor backward one character (does nothing if it’s at the beginning). 
buffer.moveCursorToStart() 
Moves the cursor to the beginning of the buffer. 
buffer.moveCursorToEnd() 
Moves the cursor to the end of the buffer. 
buffer.insertCharacter(ch) 
Inserts the character ch at the cursor position and advances the cursor past it. 
buffer.deleteCharacter() 
Deletes the character after the cursor, if any. 
buffer.display() 
Displays the buffer on cout (primarily for debugging). 
The Two-Stack Model 
• In the two-stack implementation of the EditorBuffer class, 
the characters in the buffer are stored in one of two stacks.  
The characters before the cursor are stored in a stack called 
before and the characters that follow the cursor are stored in 
a stack called after.  Characters in each stack are stored so 
that the ones close to the cursor are near the top of the stack. 
• For example, given the buffer contents 
a b c d e 
 the characters would be stored like this: 
before after 
a 
b 
c 
e 
d 
private: 
 
/* Data required to represent the two-stack form of the buffer */ 
 
    CharStack before;     /* Stack of characters before the cursor */ 
    CharStack after;      /* Stack of characters after the cursor  */ 
 
Stack-Based Private Data for Buffer 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!