fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. /*template<typename ItemType>
  4. class Node {
  5. public:
  6. 	ItemType data; // data
  7. 	Node* next; // pointer to next
  8. };
  9.  
  10. template<typename ItemType>
  11. class List {
  12. private:
  13. 	Node<ItemType>* head;
  14.  
  15. public:
  16. 	// Class constructor. Note that We don't need the Parameterized constructor with the max here.
  17. 	List(void);
  18.  
  19. 	// Destructor
  20. 	~List(void);
  21.  
  22. 	// Function: Determines whether the list is empty.
  23. 	// Pre:  List has been initialized.
  24. 	// Post: Function value = (list is empty)
  25. 	bool IsEmpty();
  26.  
  27. 	// Function: Adds newItem to the list at a specific place and returns the created node.
  28. 	// Pre:  List has been initialized.
  29. 	// Post: New item is added and the created node are returned.
  30. 	Node<ItemType>* InsertNode(int index, ItemType x);
  31.  
  32. 	// Function: Searches the list for a specific value.
  33. 	// Pre:  List has been initialized.
  34. 	// Post: Location of the value is returned if found otherwise 0 is returned
  35. 	int FindNode(ItemType x);
  36.  
  37. 	// Function: Deletes a node by its value
  38. 	// Pre:  List has been initialized.
  39. 	// Post: Node is deleted from the list.
  40. 	int DeleteNode(ItemType x);
  41.  
  42. 	int GetLength();
  43.  
  44. 	List<ItemType>* CopyList();
  45.  
  46. 	void DisplayList(void);
  47.  
  48. };
  49.  
  50. template<typename ItemType>
  51. List<ItemType>::List(void)
  52. {
  53. 	head = NULL;
  54. }
  55.  
  56. template<typename ItemType>
  57. List<ItemType>::~List(void)
  58. {
  59. 	Node<ItemType>* currNode = head;
  60. 	Node<ItemType>* nextNode = NULL;
  61. 	while (currNode != NULL) {
  62. 		nextNode = currNode->next;
  63. 		delete currNode; // destroy the current node
  64. 		currNode = nextNode;
  65. 	}
  66. }
  67.  
  68. template<typename ItemType>
  69. bool List<ItemType>::IsEmpty()
  70. {
  71. 	return head == NULL;
  72. }
  73.  
  74. template<typename ItemType>
  75. Node<ItemType>* List<ItemType>::InsertNode(int index, ItemType x)
  76. {
  77. 	if (index < 0)
  78. 		return NULL;
  79. 	int currIndex = 1;
  80. 	Node<ItemType>* currNode = head;
  81. 	while (currNode && index > currIndex) {
  82. 		//Try to locate index'th node. If it doesn't exist, return NULL
  83. 		currNode = currNode->next;
  84. 		currIndex++;
  85. 	}
  86. 	if (index > 0 && currNode == NULL)
  87. 		return NULL;
  88. 	Node<ItemType>* newNode = new Node<ItemType>;
  89. 	newNode->data = x;
  90. 	if (index == 0) {
  91. 		newNode->next = head;
  92. 		head = newNode;
  93. 	}
  94. 	else {
  95. 		newNode->next = currNode->next;
  96. 		currNode->next = newNode;
  97. 	}
  98. 	return newNode;
  99. }
  100.  
  101. template<typename ItemType>
  102. int List<ItemType>::FindNode(ItemType x)
  103. {
  104. 	Node<ItemType>* currNode = head;
  105. 	int currIndex = 1;
  106. 	while (currNode && currNode->data != x) {
  107. 		currNode = currNode->next;
  108. 		currIndex++;
  109. 	}
  110. 	if (currNode)
  111. 		return currIndex;
  112. 	return 0;
  113. }
  114.  
  115. template<typename ItemType>
  116. int List<ItemType>::DeleteNode(ItemType x)
  117. {
  118. 	Node<ItemType>* prevNode = NULL;
  119. 	Node<ItemType>* currNode = head;
  120. 	int currIndex = 1;
  121. 	while (currNode && currNode->data != x) {
  122. 		prevNode = currNode;
  123. 		currNode = currNode->next;
  124. 		currIndex++;
  125. 	}
  126. 	if (currNode) {
  127. 		if (prevNode) {
  128. 			prevNode->next = currNode->next;
  129. 			delete currNode;
  130. 		}
  131. 		else {
  132. 			head = currNode->next;
  133. 			delete currNode;
  134. 		}
  135. 		return currIndex;
  136. 	}
  137. 	return 0;
  138. }
  139.  
  140. template<typename ItemType>
  141. void List<ItemType>::DisplayList(void)
  142. {
  143. 	int num = 0;
  144. 	Node<ItemType>* currNode = head;
  145. 	while (currNode != NULL) {
  146. 		cout << currNode->data << endl;
  147. 		currNode = currNode->next;
  148. 		num++;
  149. 	}
  150. 	cout << "Number of nodes in the list: " << num << endl;
  151. }
  152. ===============================================================================================*/
  153. /*
  154. template<typename ItemType>
  155. struct Node {
  156. public:
  157. 	ItemType data; // data
  158. 	Node* next; // pointer to next
  159. };
  160.  
  161. template<typename ItemType>
  162. class CircularLinkedList {
  163. private:
  164. 	Node<ItemType>* rear;
  165.  
  166. public:
  167. 	// Class constructor. Note that We don't need the Parameterized constructor with the max here.
  168. 	CircularLinkedList();
  169.  
  170. 	// Destructor
  171. 	~CircularLinkedList();
  172.  
  173. 	void insertNode(ItemType item);
  174.  
  175. 	void deleteNode(ItemType item);
  176.  
  177. 	void Print();
  178.  
  179. 	void Rotate(int n);
  180.  
  181. 	int Count();
  182. };
  183.  
  184. template <typename ItemType>
  185. CircularLinkedList<ItemType>::CircularLinkedList()
  186. {
  187. 	rear = NULL;
  188. }
  189.  
  190. template <typename ItemType>
  191. CircularLinkedList<ItemType>::~CircularLinkedList()
  192. {
  193. 	//TODO: by students
  194. 	if (rear == NULL) // If the list is already empty, nothing to do
  195. 		return;
  196.  
  197. 	Node<ItemType>* current = rear->next; // Start from the first node
  198. 	Node<ItemType>* nextNode;
  199.  
  200. 	while (current != rear) {
  201. 		nextNode = current->next; // Store the next node
  202. 		delete current; // Delete the current node
  203. 		current = nextNode; // Move to the next node
  204. 	}
  205.  
  206. 	// Delete the last node (rear) and set rear to nullptr
  207. 	delete rear;
  208. 	rear = NULL;
  209. }
  210.  
  211. template <typename ItemType>
  212. void CircularLinkedList<ItemType>::insertNode(ItemType item)
  213. {
  214. 	Node<ItemType>* Cur = NULL;
  215. 	Node<ItemType>* Prev = NULL;
  216. 	Node<ItemType>* New = new Node<ItemType>;
  217. 	New->data = item;
  218. 	if (rear == NULL) {	// insert into empty list
  219. 		rear = New;
  220. 		rear->next = rear;
  221. 		return;
  222. 	}
  223.  
  224. 	Prev = rear;
  225. 	Cur = rear->next;
  226. 	do {				// find Prev and Cur
  227. 		if (item <= Cur->data)
  228. 			break;
  229. 		Prev = Cur;
  230. 		Cur = Cur->next;
  231. 	} while (Cur != rear->next);
  232.  
  233. 	New->next = Cur;	// revise pointers
  234. 	Prev->next = New;
  235. 	if (item > rear->data)	//revise Rear pointer if adding to end
  236. 		rear = New;
  237. }
  238.  
  239. template <typename ItemType>
  240. void CircularLinkedList<ItemType>::deleteNode(ItemType item)
  241. {
  242. 	Node<ItemType>* Cur = NULL;
  243. 	Node<ItemType>* Prev = NULL;
  244. 	if (rear == NULL) {
  245. 		cout << "Trying to delete empty list" << endl;
  246. 		return;
  247. 	}
  248.  
  249. 	Prev = rear;
  250. 	Cur = rear->next;
  251.  
  252. 	do {				// find Prev and Cur
  253. 		if (item <= Cur->data)  break;
  254. 		Prev = Cur;
  255. 		Cur = Cur->next;
  256. 	} while (Cur != rear->next);
  257.  
  258. 	if (Cur->data != item) {	// data does not exist
  259. 		cout << "Data Not Found" << endl;
  260. 		return;
  261. 	}
  262.  
  263. 	if (Cur == Prev) {		// delete single-node list
  264. 		rear = NULL;
  265. 		delete Cur;
  266. 		return;
  267. 	}
  268.  
  269. 	if (Cur == rear)		// revise Rear pointer if deleting end
  270. 		rear = Prev;
  271. 	Prev->next = Cur->next;	// revise pointers
  272. 	delete Cur;
  273. }
  274.  
  275. template <typename ItemType>
  276. void CircularLinkedList<ItemType>::Print() {
  277.  
  278. 	if (rear != NULL) {
  279. 		Node<ItemType>* curr = rear->next;
  280.  
  281. 		do
  282. 		{
  283. 			cout << curr->data << " ";
  284. 			curr = curr->next;
  285. 		} while (curr != rear->next);
  286.  
  287. 		cout << endl;
  288. 	}
  289. }
  290.  
  291. template <typename ItemType>
  292. int CircularLinkedList<ItemType>::Count() {
  293.  
  294. 	if (rear == NULL)
  295. 		return 0;
  296.  
  297. 	Node<ItemType>* curr = rear->next;
  298. 	int count = 0;
  299. 	do
  300. 	{
  301. 		count++;
  302. 		curr = curr->next;
  303. 	} while (curr != rear->next);
  304.  
  305. 	return count;
  306. }
  307.  
  308. template <typename ItemType>
  309. void CircularLinkedList<ItemType>::Rotate(int n) {
  310.  
  311. 	if (n == 0)
  312. 		return;
  313.  
  314. 	if (rear != NULL) {
  315. 		n = Count() - n;
  316. 		Node<ItemType>* curr = rear->next;
  317.  
  318. 		for (int i = 0; i < n - 1; i++)
  319. 		{
  320. 			curr = curr->next;
  321. 		}
  322. 		rear = curr;
  323. 	}
  324. }
  325. ==========================================================================================*/
  326. /*
  327. template<typename ItemType>
  328. struct Node {
  329. public:
  330. 	ItemType data; // data
  331. 	Node* next; // pointer to next
  332. 	Node* prev; // pointer to previous
  333. };
  334.  
  335. //Doubly Linked Lists with Dummy Head Node
  336. template<typename ItemType>
  337. class DoublyLinkedList {
  338. private:
  339. 	Node<ItemType>* head;
  340. public:
  341. 	// Class constructor. Note that We don't need the Parameterized constructor with the max here.
  342. 	DoublyLinkedList(void);
  343.  
  344. 	// Destructor
  345. 	~DoublyLinkedList(void);
  346.  
  347. 	bool isEmpty();
  348.  
  349. 	Node<ItemType>* searchNode(ItemType item);
  350.  
  351. 	void insertNode(ItemType item);
  352.  
  353. 	void deleteNode(ItemType item);
  354.  
  355. 	void Print();
  356.  
  357. 	int Count();
  358.  
  359. 	void Rotate(int n);
  360. };
  361.  
  362. template <typename ItemType>
  363. void DoublyLinkedList<ItemType>::Print()
  364. {
  365. 	Node<ItemType>* curr = head->next;
  366. 	while (curr != head) {
  367. 		cout << curr->data << " ";
  368. 		curr = curr->next;
  369. 	}
  370. 	cout << endl;
  371. }
  372.  
  373. template <typename ItemType>
  374. int DoublyLinkedList<ItemType>::Count()
  375. {
  376. 	int count = 0;
  377. 	Node<ItemType>* curr = head->next;
  378. 	while (curr != head) {
  379. 		count++;
  380. 		curr = curr->next;
  381. 	}
  382. 	return count;
  383. }
  384.  
  385. template <typename ItemType>
  386. void DoublyLinkedList<ItemType>::Rotate(int n)
  387. {
  388. 	if (n == 0)
  389. 		return;
  390.  
  391. 	Node<ItemType>* firstNode = head->next;
  392. 	Node<ItemType>* lastNode = head->prev;
  393.  
  394. 	Node<ItemType>* curr = head->prev;
  395. 	for (int i = 0; i < n; i++)
  396. 	{
  397. 		curr = curr->prev;
  398. 	}
  399.  
  400. 	firstNode->prev = lastNode;
  401. 	lastNode->next = firstNode;
  402.  
  403. 	head->prev = curr;
  404. 	head->next = curr->next;
  405.  
  406. 	curr->next->prev = head;
  407. 	curr->next = head;
  408. }
  409.  
  410. template <typename ItemType>
  411. bool DoublyLinkedList<ItemType>::isEmpty()
  412. {
  413. 	return (head->next == head);
  414. }
  415.  
  416. template <typename ItemType>
  417. Node<ItemType>* DoublyLinkedList<ItemType>::searchNode(ItemType item)
  418. {
  419. 	Node<ItemType>* Cur = head->next;
  420.  
  421. 	while (Cur != head) {
  422.  
  423. 		if (Cur->data == item)
  424. 			return Cur;
  425.  
  426. 		if ((Cur->data) < item)
  427. 			Cur = Cur->next;
  428. 		else
  429. 			break;
  430. 	}
  431.  
  432. 	return NULL;
  433. }
  434.  
  435. template <typename ItemType>
  436. DoublyLinkedList<ItemType>::DoublyLinkedList()
  437. {
  438. 	head = new Node<ItemType>;
  439. 	head->next = head;
  440. 	head->prev = head;
  441. }
  442.  
  443. template <typename ItemType>
  444. DoublyLinkedList<ItemType>::~DoublyLinkedList()
  445. {
  446. 	//TODO: By students.
  447.  
  448. 	// Start from the node after the head
  449. 	Node<ItemType>* current = head->next;
  450. 	Node<ItemType>* nextNode;
  451.  
  452. 	// Traverse the list until we reach the head node again
  453. 	while (current != head) {
  454. 		nextNode = current->next; // Store the next node
  455. 		delete current; // Delete the current node
  456. 		current = nextNode; // Move to the next node
  457. 	}
  458.  
  459. 	// Delete the head node
  460. 	delete head;
  461. }
  462.  
  463. template <typename ItemType>
  464. void DoublyLinkedList<ItemType>::insertNode(ItemType item)
  465. {
  466. 	Node<ItemType>* New = NULL;
  467. 	Node<ItemType>* Cur = NULL;
  468. 	New = new Node<ItemType>;
  469. 	New->data = item;
  470.  
  471. 	Cur = head->next;
  472. 	while (Cur != head) { //position Cur for insertion
  473. 		if ((Cur->data) < item)
  474. 			Cur = Cur->next;
  475. 		else
  476. 			break;
  477. 	}
  478.  
  479. 	New->next = Cur;
  480. 	New->prev = Cur->prev;
  481. 	Cur->prev = New;
  482. 	(New->prev)->next = New;
  483. }
  484.  
  485. template <typename ItemType>
  486. void DoublyLinkedList<ItemType>::deleteNode(ItemType item)
  487. {
  488. 	Node<ItemType>* Cur;
  489. 	Cur = searchNode(item);
  490.  
  491. 	if (Cur != NULL) {
  492. 		Cur->prev->next = Cur->next;
  493. 		Cur->next->prev = Cur->prev;
  494. 		delete Cur;
  495. 	}
  496. }
  497. =======================================================================================*/
  498. /*
  499. // The class definition for QueueType using templates 
  500. class FullQueue
  501. 	// Exception class thrown by enqueue when Queue is full.
  502. {
  503. };
  504.  
  505. class EmptyQueue
  506. 	// Exception class thrown by dequeue and first when Queue is empty.
  507. {
  508. };
  509. template<typename ItemType>
  510. class QueueType
  511. {
  512. private:
  513. 	int front;
  514. 	int rear;
  515. 	ItemType* items;
  516. 	int maxQue;
  517. 	int counter;
  518.  
  519. public:
  520.  
  521. 	// Class constructor.
  522. 	QueueType();
  523.  
  524. 	// Parameterized constructor.
  525. 	QueueType(int max);
  526.  
  527. 	// Destructor
  528. 	~QueueType();
  529.  
  530. 	// Function: Determines whether the queue is full.
  531. 	// Pre:  Queue has been initialized.
  532. 	// Post: Function value = (queue is full)
  533. 	bool IsFull() const;
  534.  
  535. 	// Function: Determines whether the queue is empty.
  536. 	// Pre:  Queue has been initialized.
  537. 	// Post: Function value = (queue is empty)
  538. 	bool IsEmpty() const;
  539.  
  540. 	// Function: makes the queue empty.
  541. 	// Pre:  Queue has been initialized.
  542. 	// Post: Queue is empty
  543. 	void MakeEmpty();
  544.  
  545. 	// Function: Adds newItem to the end of the queue.
  546. 	// Pre:  Queue has been initialized.
  547. 	// Post: If (Queue is full), FullQueue exception is thrown;
  548. 	//       otherwise, newItem is at the end of the queue.
  549. 	void Enqueue(ItemType);
  550.  
  551. 	// Function: Removes item from the queue that was inserted.
  552. 	// Pre:  Queue has been initialized.
  553. 	// Post: If (Queue is empty), EmptyQueue exception is thrown;
  554. 	//       otherwise, Removes item from the queue that was inserted
  555. 	ItemType Dequeue();
  556.  
  557. 	// Function: Returns a copy of item on the queue.
  558. 	// Pre:  Queue has been initialized.
  559. 	// Post: If (queue is empty), EmptyQueue exception is thrown;
  560. 	//       otherwise, Removes item from the queue that was inserted
  561. 	ItemType First();
  562.  
  563. 	int GetLength();
  564.  
  565. 	void DisplayQueue();
  566. };
  567.  
  568. template<typename ItemType>
  569. QueueType<ItemType>::QueueType()
  570. {
  571. 	maxQue = 501; //Default
  572. 	front = maxQue - 1;
  573. 	rear = maxQue - 1;
  574. 	items = new ItemType[maxQue];
  575. 	counter = 0;
  576. }
  577.  
  578. template<typename ItemType>
  579. QueueType<ItemType>::QueueType(int max)
  580. {
  581. 	maxQue = max;
  582. 	front = maxQue - 1;
  583. 	rear = maxQue - 1;
  584. 	items = new ItemType[maxQue];
  585. 	counter = 0;
  586. }
  587.  
  588. template<typename ItemType>
  589. QueueType<ItemType>::~QueueType()
  590. {
  591. 	delete[] items;
  592. }
  593.  
  594. template<typename ItemType>
  595. bool QueueType<ItemType>::IsFull() const
  596. {
  597. 	//return ((rear + 1) % maxQue == front);
  598. 	return counter == maxQue;
  599. }
  600.  
  601. template<typename ItemType>
  602. bool QueueType<ItemType>::IsEmpty() const
  603. {
  604. 	//return (rear == front);
  605. 	return counter == 0;
  606. }
  607.  
  608. template<typename ItemType>
  609. void QueueType<ItemType>::MakeEmpty()
  610. {
  611. 	front = maxQue - 1;
  612. 	rear = maxQue - 1;
  613. 	counter = 0;
  614. }
  615.  
  616. template<typename ItemType>
  617. void QueueType<ItemType>::Enqueue(ItemType newItem)
  618. {
  619. 	if (IsFull())
  620. 	{
  621. 		throw FullQueue();
  622. 	}
  623. 	else
  624. 	{
  625. 		rear = (rear + 1) % maxQue;
  626. 		counter++;
  627. 		items[rear] = newItem;
  628. 	}
  629. }
  630.  
  631. template<typename ItemType>
  632. ItemType QueueType<ItemType>::Dequeue()
  633. {
  634. 	if (IsEmpty())
  635. 	{
  636. 		throw EmptyQueue();
  637. 	}
  638. 	else
  639. 	{
  640. 		front = (front + 1) % maxQue;
  641. 		counter--;
  642. 		return items[front];
  643. 	}
  644. }
  645.  
  646. template<typename ItemType>
  647. ItemType QueueType<ItemType>::First()
  648. {
  649. 	if (IsEmpty())
  650. 	{
  651. 		throw EmptyQueue();
  652. 	}
  653. 	else
  654. 	{
  655. 		return items[(front + 1) % maxQue];
  656. 	}
  657. }
  658.  
  659. template<typename ItemType>
  660. int QueueType<ItemType>::GetLength()
  661. {
  662. 	return counter;
  663. }
  664.  
  665. template<typename ItemType>
  666. void QueueType<ItemType>::DisplayQueue() {
  667.  
  668. 	for (int i = 1; i <= GetLength(); i++)
  669. 	{
  670. 		ItemType temp = Dequeue();
  671. 		cout << temp << " ";
  672. 		Enqueue(temp);
  673. 	}
  674. 	cout << endl;
  675.  
  676. }
  677. ===========================================================================================*/
  678.  
  679. /*
  680. template<class ItemType>
  681. class QueueTypeLinked {
  682. public:
  683. 	QueueTypeLinked();
  684. 	~QueueTypeLinked();
  685. 	void MakeEmpty();
  686. 	bool IsEmpty() const;
  687. 	bool IsFull() const;
  688. 	void Enqueue(ItemType);
  689. 	ItemType Dequeue();
  690. 	int Length();
  691. private:
  692. 	Node<ItemType>* qFront;
  693. 	Node<ItemType>* qRear;
  694. };
  695.  
  696. template<class ItemType>
  697. QueueTypeLinked<ItemType>::QueueTypeLinked()
  698. {
  699. 	qFront = NULL;
  700. 	qRear = NULL;
  701. }
  702.  
  703. template<class ItemType>
  704. void QueueTypeLinked<ItemType>::MakeEmpty()
  705. {
  706. 	Node<ItemType>* tempPtr;
  707.  
  708. 	while (qFront != NULL) {
  709. 		tempPtr = qFront;
  710. 		qFront = qFront->next;
  711. 		delete tempPtr;
  712. 	}
  713. 	qRear = NULL;
  714. }
  715.  
  716. template<class ItemType>
  717. QueueTypeLinked<ItemType>::~QueueTypeLinked()
  718. {
  719. 	MakeEmpty();
  720. }
  721.  
  722. template<class ItemType>
  723. bool QueueTypeLinked<ItemType>::IsEmpty() const
  724. {
  725. 	return(qFront == NULL);
  726. }
  727.  
  728. template<class ItemType>
  729. bool QueueTypeLinked<ItemType>::IsFull() const
  730. {
  731. 	Node<ItemType>* ptr;
  732.  
  733. 	//We test to create a node in the memory (It its created then the memory isn't full)
  734. 	ptr = new Node<ItemType>;
  735. 	if (ptr == NULL)
  736. 		return true;
  737. 	else {
  738. 		delete ptr;
  739. 		return false;
  740. 	}
  741. }
  742.  
  743. template<class ItemType>
  744. void QueueTypeLinked<ItemType>::Enqueue(ItemType newItem)
  745. {
  746. 	Node<ItemType>* newNode;
  747.  
  748. 	newNode = new Node<ItemType>;
  749. 	newNode->data = newItem;
  750. 	newNode->next = NULL;
  751. 	if (qRear == NULL)
  752. 		qFront = newNode;
  753. 	else
  754. 		qRear->next = newNode;
  755. 	qRear = newNode;
  756. }
  757.  
  758. template<class ItemType>
  759. ItemType QueueTypeLinked<ItemType>::Dequeue()
  760. {
  761. 	Node<ItemType>* tempPtr;
  762.  
  763. 	tempPtr = qFront;
  764. 	ItemType item = qFront->data;
  765. 	qFront = qFront->next;
  766. 	if (qFront == NULL)
  767. 		qRear = NULL;
  768. 	delete tempPtr;
  769. 	return item;
  770. }
  771.  
  772. template<class ItemType>
  773. int QueueTypeLinked<ItemType>::Length()
  774. {
  775. 	QueueTypeLinked<ItemType> tempQ;
  776. 	ItemType item;
  777. 	int length = 0;
  778.  
  779. 	while (!IsEmpty())
  780. 	{
  781. 		item=Dequeue();
  782. 		tempQ.Enqueue(item);
  783. 		length++;
  784. 	}
  785.  
  786. 	while (!tempQ.IsEmpty())
  787. 	{
  788. 		item=tempQ.Dequeue();
  789. 		Enqueue(item);
  790. 	}
  791.  
  792. 	return length;
  793. }
  794. =====================================================================================*/
  795. /*
  796. // The class definition for StackType using templates 
  797. class FullStack
  798. 	// Exception class thrown by Push when stack is full.
  799. {
  800. };
  801.  
  802. class EmptyStack
  803. 	// Exception class thrown by Pop and Top when stack is empty.
  804. {
  805. };
  806.  
  807.  
  808. template<typename ItemType>
  809. class StackType
  810. {
  811. private:
  812. 	int top;
  813. 	int maxStack;
  814. 	ItemType* items;
  815.  
  816. public:
  817.  
  818. 	// Class constructor.
  819. 	StackType();
  820.  
  821. 	// Parameterized constructor.
  822. 	StackType(int max);
  823.  
  824. 	// Destructor
  825. 	~StackType();
  826.  
  827. 	// Function: Determines whether the stack is full.
  828. 	// Pre:  Stack has been initialized.
  829. 	// Post: Function value = (stack is full)
  830. 	bool IsFull() const;
  831.  
  832. 	// Function: Determines whether the stack is empty.
  833. 	// Pre:  Stack has been initialized.
  834. 	// Post: Function value = (stack is empty)
  835. 	bool IsEmpty() const;
  836.  
  837. 	// Function: makes the stack empty.
  838. 	// Pre:  Stack has been initialized.
  839. 	// Post: Stack is empty
  840. 	void MakeEmpty() const;
  841.  
  842. 	// Function: Adds newItem to the top of the stack.
  843. 	// Pre:  Stack has been initialized.
  844. 	// Post: If (stack is full), FullStack exception is thrown;
  845. 	//       otherwise, newItem is at the top of the stack.
  846. 	void Push(ItemType item);
  847.  
  848. 	// Function: Removes top item from the stack.
  849. 	// Pre:  Stack has been initialized.
  850. 	// Post: If (stack is empty), EmptyStack exception is thrown;
  851. 	//       otherwise, top element has been removed from stack.
  852. 	ItemType Pop();
  853.  
  854. 	// Function: Returns a copy of top item on the stack.
  855. 	// Pre:  Stack has been initialized.
  856. 	// Post: If (stack is empty), EmptyStack exception is thrown;
  857. 	//       otherwise, top element has been removed from stack.
  858. 	ItemType Top();
  859.  
  860. 	int GetLength();
  861.  
  862. 	void Print();
  863. };
  864.  
  865. // The function definitions for class StackType.
  866.  
  867. template<typename ItemType>
  868. StackType<ItemType>::StackType(int max)
  869. {
  870. 	maxStack = max;
  871. 	top = -1;
  872. 	items = new ItemType[maxStack];
  873. }
  874.  
  875. template<typename ItemType>
  876. StackType<ItemType>::StackType()
  877. {
  878. 	maxStack = 500;  //Default
  879. 	top = -1;
  880. 	items = new ItemType[maxStack];
  881. }
  882.  
  883. template<typename ItemType>
  884. bool StackType<ItemType>::IsEmpty() const
  885. {
  886. 	return (top == -1);
  887. }
  888.  
  889. template<typename ItemType>
  890. void StackType<ItemType>::MakeEmpty() const
  891. {
  892. 	top = -1;
  893. }
  894.  
  895. template<typename ItemType>
  896. bool StackType<ItemType>::IsFull() const
  897. {
  898. 	return (top == maxStack - 1);
  899. }
  900.  
  901. template<typename ItemType>
  902. void StackType<ItemType>::Push(ItemType newItem)
  903. {
  904.  
  905. 	if (IsFull())
  906. 		throw FullStack();
  907. 	top++;
  908. 	items[top] = newItem;
  909. }
  910.  
  911. template<typename ItemType>
  912. ItemType StackType<ItemType>::Pop()
  913. {
  914. 	if (IsEmpty())
  915. 		throw EmptyStack();
  916. 	return items[top--];
  917. }
  918.  
  919. template<typename ItemType>
  920. ItemType StackType<ItemType>::Top()
  921. {
  922. 	if (IsEmpty())
  923. 		throw EmptyStack();
  924. 	return items[top];
  925. }
  926.  
  927. template<typename ItemType>
  928. int StackType<ItemType>::GetLength()
  929. {
  930. 	return top + 1;
  931. }
  932.  
  933. template<typename ItemType>
  934. StackType<ItemType>::~StackType()
  935. {
  936. 	delete[] items;
  937. }
  938. ================================================================================================*/
  939. /*
  940. template<class ItemType>
  941. class StackTypeLinked {
  942. public:
  943. 	StackTypeLinked();
  944. 	~StackTypeLinked();
  945. 	void MakeEmpty();
  946. 	bool IsEmpty() const;
  947. 	bool IsFull() const;
  948. 	void Push(ItemType);
  949. 	ItemType Pop();
  950. private:
  951. 	Node<ItemType>* topPtr;
  952. };
  953.  
  954. template<class ItemType>
  955. StackTypeLinked<ItemType>::StackTypeLinked()
  956. {
  957. 	topPtr = NULL;
  958. }
  959.  
  960. template<class ItemType>
  961. void StackTypeLinked<ItemType>::MakeEmpty()
  962. {
  963. 	Node<ItemType>* tempPtr;
  964.  
  965. 	while (topPtr != NULL) {
  966. 		tempPtr = topPtr;
  967. 		topPtr = topPtr->next;
  968. 		delete tempPtr;
  969. 	}
  970. }
  971.  
  972. template<class ItemType>
  973. StackTypeLinked<ItemType>::~StackTypeLinked()
  974. {
  975. 	MakeEmpty();
  976. }
  977.  
  978. template<class ItemType>
  979. bool StackTypeLinked<ItemType>::IsEmpty() const
  980. {
  981. 	return(topPtr == NULL);
  982. }
  983.  
  984. template<class ItemType>
  985. bool StackTypeLinked<ItemType>::IsFull() const
  986. {
  987. 	Node<ItemType>* location;
  988.  
  989. 	//We test to create a node in the memory (It its created then the memory isn't full)
  990. 	location = new Node<ItemType>;
  991. 	if (location == NULL)
  992. 		return true;
  993. 	else {
  994. 		delete location;
  995. 		return false;
  996. 	}
  997. }
  998.  
  999. template<class ItemType>
  1000. void StackTypeLinked<ItemType>::Push(ItemType newItem)
  1001. {
  1002. 	Node<ItemType>* location;
  1003.  
  1004. 	location = new Node<ItemType>;
  1005. 	location->data = newItem;
  1006. 	location->next = topPtr;
  1007. 	topPtr = location;
  1008. }
  1009.  
  1010. template<class ItemType>
  1011. ItemType StackTypeLinked<ItemType>::Pop()
  1012. {
  1013. 	Node<ItemType>* tempPtr;
  1014.  
  1015. 	ItemType item = topPtr->data;
  1016. 	tempPtr = topPtr;
  1017. 	topPtr = topPtr->next;
  1018. 	delete tempPtr;
  1019. 	return item;
  1020. }
  1021.  
  1022.  
  1023. ========================================================================================*/
  1024.  
  1025. int main(){
  1026.  
  1027.     return 0;
  1028. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PR20he
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!