1
Kỹ thuậtlậptrình
Chương 3 – Mộtsố cấutrúcdữ
liệucơ bản
Nội dung
1. Stack
1. Định nghĩa
2. Cài đặt
2. Queue
1. Định nghĩa
2. Cài đặt
3. Case study: Mô phỏng sân bay
3. Stack và Queue kếtnối
4. List
3.1. Stack
Định nghĩaStack
 Stack: là danh sách mà xóa và thêm phầntử
bắtbuộcphảicùngđượcthựchiệntạimột
đầuduynhất(đỉnh)
5
3
2
7
2
5
3
Push
7
Pop
Pop
top

precondition: None.
postcondition: The Stack exists and is initialized
to be empty.
Kiểuphầntử
 Trong các ứng dụng khác nhau, Stack chứa
các phầntử có kiểu khác nhau
 int, float, …
 Sử dụng Stack_entry làm kiểuphầntử
 Ngườidùngcóthể lựachọnkiểuphầntử:
 typedef char Stack_entry;
Æ cài đặt không bị thay đổi
Xử lý lỗi
 Các thao tác không hợp pháp:
 Rút phầntử từ Stack rỗng Æ underflow
 Thêm phầntử vào stack đầy Æ overflow
 Sử dụng kiểuliệt kê Error_code:
 success
 underflow
 overflow
Thiếtkế hàm thành viên
Error_code Stack :: pop( );
precondition: None.
postcondition: If the Stack is not empty, the top of the
Stack is removed. If the Stack is empty,
an Error_code of underflow is returned
and the Stack is left unchanged.
Error_code Stack :: push(const Stack_entry &item);
precondition: None.
postcondition: If the Stack is not full, item is added to
the top of the Stack. If the Stack is full, an

Post: If the Stack is not empty, the top of the Stack is
returned in item. If the Stack is empty an
Error_code of underflow is returned. */
{
Error_code outcome = success;
if (count == 0)
outcome = underflow;
else
item = entry[count − 1];
return outcome;
}
3.2. Queue
Định nghĩa Queue
 Queue: là danh sách mà việc thêm phầntử
phải đượcthựchiệntạimột đầucònxóa
phầntử phảithựchiệntại đầukia.
Thêm
(Enqueue)
Xóa
(Dequeue)
CuốiĐầu
• Queue là mộtkiểucấu trúc FIFO: First In First Out
Ví dụ của Queue trong thựctế
4
Cài đặt Queue
 Kiểuphầntử: Queue_entry
 Các thao tác:
Queue :: Queue( );
postcondition: The Queue has been created and is
initialized to be empty.

 public:
 Queue( );
 bool empty( ) const;
 Error_code serve( );
 Error_code append(const Queue_entry &item);
 Error_code retrieve(Queue_entry &item) const;
 private:
 int count;
 int front, rear;
 Queue_entry entry[maxqueue];
 };
Cài đặt
 Mộtsố thao tác cầnthiết khác:
 clear
 full
 size
 serve_and_retrieve
5
bool Queue :: full( ) const;
postcondition: Return true if the Queue is full; return
false otherwise.
void Queue :: clear( );
postcondition: All entries in the Queue have been
removed; it is now empty.
int Queue :: size( ) const;
postcondition: Return the number of entries in the
Queue.
Error_code Queue :: serve_and_retrieve(Queue_entry &item);
postcondition: Return underflow if the Queue is empty.
Otherwise remove and copy the item at the

6
Stack kếtnối
class Stack {
public:
Stack( );
bool empty( ) const;
Error_code push(const Stack_entry &item);
Error_code pop( );
Error_code top(Stack_entry &item) const;
private:
Node *top_node;
};
Thêm phầntử mới
 Stack rỗng:
 top_node = NULL
 Thêm phầntử mới (item) làm phầntửđỉnh:
Node *new_top = new Node(item, top_node);
top_node = new_top;
Stack::push
Error_code Stack :: push(const Stack_entry &item)
/* Post: Stack_entry item is added to the top of the
Stack; returns success or returns a code of overflow
if dynamic memory is exhausted. */
{
Node *new_top = new Node(item, top_node);
if (new_top == NULL) return overflow;
top_node = new_top;
return success;
}
Xóa phầntửđầu

{
Node *new_top, *new_copy, *original_node = original.top_node;
if (original_node == NULL) new_top = NULL;
else { // Duplicate the linked nodes
new_copy = new_top = new Node(original_node->entry);
while (original_node->next != NULL) {
original_node = original_node->next;
new_copy->next = new Node(original_node->entry);
new_copy = new_copy->next;
}
}
while (!empty( )) // Clean out old Stack entries
pop( );
top_node = new_top; // and replace them with new entries.
return *this;
}
Hàm tạo copy
Stack :: Stack(const Stack &original) // copy constructor
/* Post: The Stack is initialized as a copy of Stack original. */
{
Node *new_copy, *original_node = original.top_node;
if (original_node == NULL) top_node = NULL;
else { // Duplicate the linked nodes.
top_node = new_copy = new Node(original_node->entry);
while (original_node->next != NULL) {
original_node = original_node->next;
new_copy->next = new Node(original_node->entry);
new_copy = new_copy->next;
}
}

Queue(const Queue &original);
void operator = (const Queue &original);
protected:
Node *front, *rear;
};
Hàm tạo
Queue :: Queue( )
/* Post: The Queue is initialized to be empty. */
{
front = rear = NULL;
}
Thêm mộtphầntử
Error_code Queue :: append(const Queue_entry &item)
/* Post: Add item to the rear of the Queue and return a code of
success or return
a code of overflow if dynamic memory is exhausted. */
{
Node *new_rear = new Node(item);
if (new_rear == NULL) return overflow;
if (rear == NULL) front = rear = new_rear;
else {
rear->next = new_rear;
rear = new_rear;
}
return success;
}
Xóa mộtphầntử
Error_code Queue :: serve( )
/* Post: The front of the Queue is removed. If the Queue is empty,
return an